# 给你一个字符串 s，找到 s 中最长的 回文 子串。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
#  
# 
#  示例 2： 
# 
#  
# 输入：s = "cbbd"
# 输出："bb"
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= s.length <= 1000 
#  s 仅由数字和英文字母组成 
#  
# 
#  Related Topics 双指针 字符串 动态规划 👍 7438 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """


        """
        有两种情况:1奇数回文,2偶数回文
        
        """

        # 辅助函数：从中心向两边扩展，返回最长回文子串,left, right分别代表左右指针的索引

        max_palindrome = ''
        ou = ""
        def expand_around_center(left, right):
            while left>=0 and right<len(s) and s[left] == s[right]:
                left-=1
                right+=1
            return s[left+1:right]
#       遍历s的每个字符
        for index,item in enumerate(s):
            """ 
            1.如果倒数第二个字符不等于倒数第一个字符,那么最后两个字符就肯定构不成偶数回文,索引可以加上index <len(s)-1的条件,即不考虑最后一个字符
            2.字符是否与下一个字符相等，决定的是偶数回文的存在性，而不是奇数回文的存在性。
            3.字符与下一个字符相等,仍不能排除它可以组成奇数长度的回文,比如aaa,第二个a和第三个a相等,但是还是组成了长度为3的回文aaa
            4.字符与下一个字符不相等,绝对可以排除它可以组成偶数长度的回文
            """
            ji = expand_around_center(index, index)
            if index < len(s)-1 and item == s[index+1]:
                ou = expand_around_center(index, index + 1)

            # 更新最长回文
            if len(ji) > len(max_palindrome):
                max_palindrome = ji
            if len(ou) > len(max_palindrome):
                max_palindrome = ou
        return max_palindrome

# leetcode submit region end(Prohibit modification and deletion)
if __name__ == '__main__':
    print(Solution().longestPalindrome(s="babad"))